package algorithmlearn.sort;

/*
二分查找  对 有重复 数据的有序的数据集合
针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0
 */
public class BinarySearch2 {
    public static void main(String[] args) {
        int[] array = {1, 2, 2, 4, 5, 6, 7, 7, 8, 8, 8, 9, 10, 16, 17, 17, 19, 20, 23};
        System.out.println(bsearch(array, array.length,8));
        System.out.println(bsearch2(array, array.length,8));
    }
    //二分查找的递归与非递归实现

    //二分查找的非递归实现
    public static int bsearch(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == 0) || (a[mid - 1] != value)) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }

    //二分查找 简介写法
    public static int bsearch2(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (low < n && a[low]==value) return low;
        else return -1;
    }
}
